class AnimalShelf {
public:
    AnimalShelf() {
    }
    
    void enqueue(vector<int> animal) {
        if(animal[1] == 0)
            qcat.push(animal[0]);
        else
            qdog.push(animal[0]);
        mp[animal[0]] = animal[1];
    }
    
    vector<int> dequeueAny() {
        int kind, num;
        if(qcat.empty() && qdog.empty())
            return { -1, -1 };
        else if(qcat.empty()) 
        {
            kind = mp[qdog.front()];
            num = qdog.front();
        }
        else if(qdog.empty())
        {
            kind = mp[qcat.front()];
            num = qcat.front();
        }
        else
        {
            if(qdog.front() < qcat.front())
            {
                kind = mp[qdog.front()];
                num = qdog.front();
            }
            else
            {
                kind = mp[qcat.front()];
                num = qcat.front();
            }
        }
        mp.erase(num);
        if(kind) qdog.pop();
        else qcat.pop();
        return { num, kind };
    }
    
    vector<int> dequeueDog() {
        if(qdog.empty())
            return { -1, -1 };
        int num = qdog.front();
        qdog.pop();
        return { num, mp[num] };
    }
    
    vector<int> dequeueCat() {
        if(qcat.empty())
            return { -1, -1 };
        int num = qcat.front();
        qcat.pop();
        return { num, mp[num] };
    }
    queue<int> qcat;
    queue<int> qdog;
    unordered_map<int, bool> mp;
};

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf* obj = new AnimalShelf();
 * obj->enqueue(animal);
 * vector<int> param_2 = obj->dequeueAny();
 * vector<int> param_3 = obj->dequeueDog();
 * vector<int> param_4 = obj->dequeueCat();
 */
